package through;

/**
 * @author zhangjiayuan@qipeipu.com
 * @date 2019/1/6 13:45
 * @since 1.0.0
 */
public class Kmp2 {
    static int[] getNext(String p) {
        char[] psChar = p.toCharArray();
        int[] next = new int[psChar.length];
        int i = 0, j = -1;
        next[0] = j;
        while (i < psChar.length - 1) {
            if (j == -1 || psChar[i] == psChar[j]) {
                i++;
                j++;
                next[i] = j;
            } else
                j = next[j];
        }
        return next;
    }

    public static void main(String[] args) {
        int[] result = Kmp2.getNext("abababca");
        for (int res : result) {
            System.out.print(res + " ");
        }
    }
}
